P6288 [COCI2016-2017#1] Kralj

COCI2016-2017#1题解

因为题面不一样，作者也懒得改，所以以下兽人指侏儒，骑士指精灵

1.40分思路

​ 兽王给每个勇士选择的对手都是 1 号兽人，那么，GM所指定骑士的顺序就一定是兽人的编号，即第i个骑士对第i个兽人。现在我们只需找一种骑士的排法，使得胜场数最大。

​ 贪心的想，最强的骑士对比他弱的兽人中最强的，第二强的骑士对比他弱的兽人中最强的······直到某一位骑士无法打败任何一人。可以排序后用单调性优化。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 500000;
int n,a[ MAXN + 5 ],p[ MAXN + 5 ],v[ MAXN + 5 ];

bool cmp( const int &x , const int &y ) {
	return x > y;
}
int main( ) {
	//freopen("Kralj.in","r",stdin);
	//freopen("Kralj.out","w",stdout);
	scanf("%d",&n);
	for( int i = 1 ; i <= n ; i ++ )
		scanf("%d",&a[ i ]);
	for( int i = 1 ; i <= n ; i ++ )
		scanf("%d",&p[ i ]);
	for( int i = 1 ; i <= n ; i ++ )
		scanf("%d",&v[ i ]);
	sort( p + 1 , p + n + 1 , cmp );
	sort( v + 1 , v + n + 1 , cmp );
	
	int Ans = 0 , last = 1;
	for( int i = 1 ; i <= n ; i ++ ) {
		for( int j = last ; j <= n ; j ++ ) {
			if( v[ i ] > p[ j ] ) {
				Ans ++;
				last = j + 1;
				break;
			}
			if( j == n && v[ i ] < p[ j ] ) last = n + 1;
		}
			
		if( last == n + 1 ) break;
	}
	printf("%d",Ans);
	return 0;
}

2.100分思路

假设骑士走到$a_i$后就停下，不继续向前找兽人，我们用$pre[i]$表示$i$与$i$之前的节点骑士的个数。

当一个区间$[i,j]$内的骑士多于该区间的兽人时，可表示为：

$pre[i]-pre[j-1]>i-j+1$

移项得：

$pre[i]-i>pre[j-1]-(j-1)$

令$P_i=pre[i]-i$，则$P_i>P_{j-1}$。由定义可得，$P_i$的意思是这个点之前的骑士与兽人的数量之差，我们设$P_m=min\{p_i\}$。则一定没有骑士从 $m$ 走到 $m+1$ 。证明如下：

因为$P_m$最小，所以对于任意$P_i$，$P_m-P_i≤0$，即m之前的骑士都能找到对应的兽人。所以我们可以在 $m$ 处剖开链，贪心模拟。

​ 我们从 $m+1$ 开始，用 $S$ 表示没有坐好的骑士的集合。每次到达新的点，先加入停留在这个点上的所有骑士。现在可能有多个骑士对一个兽人，显然我们应该用实力高于这个兽人中实力最小的骑士来面对它，可以用二分求出，答案加 $1$。剩下的骑士向前移。如果没有骑士大于兽人的实力，就将骑士实力最弱的留下当炮灰。

注意跑环时，$n+1$就是$1$，特判一下。

#include <cstdio>
#include <vector>
#include <set>
using namespace std;

const int MAXN = 500000;
int n,a[ MAXN + 5 ],p[ MAXN + 5 ],v[ MAXN + 5 ];
int pre[ MAXN + 5 ],s[ MAXN + 5 ];
int Min = 0x3f3f3f3f , Min_dex;
vector< int > vec[ MAXN + 5 ];
set< int > Set;

int solve( int x ) {
	int Ans = 0 , tot = 1;
	while( tot <= n ) {
		for( int i = 0 ; i < vec[ x ].size( ) ; i ++ )
			Set.insert( vec[ x ][ i ] );
		auto it = Set.lower_bound( p[ x ] );
		if( it == Set.end() )
			Set.erase( Set.begin() );
		else {
			Set.erase( it );
			Ans ++;
		}
		tot ++;
		x = ( x + 1 ) > n ? 1 : x + 1;
	}
	return Ans;
}
int main( ) {
	//freopen("Kralj.in","r",stdin);
	//freopen("Kralj.out","w",stdout);
	scanf("%d",&n);
	for( int i = 1 ; i <= n ; i ++ )
		scanf("%d",&a[ i ]);
	for( int i = 1 ; i <= n ; i ++ )
		scanf("%d",&p[ i ]);
	for( int i = 1 ; i <= n ; i ++ )
		scanf("%d",&v[ i ]);
	for( int i = 1 ; i <= n ; i ++ ) {
		pre[ a[ i ] ] ++;
		vec[ a[ i ] ].push_back( v[ i ] );
	}
	for( int i = 1 ; i <= n ; i ++ ) {
		pre[ i ] += pre[ i - 1 ];
		s[ i ] = pre[ i ] - i;
		if( s[ i ] < Min ) {
			Min = s[ i ];
			Min_dex = i;
		}
	}
	int cut = ( Min_dex + 1 ) > n ? 1 : ( Min_dex + 1 );
	printf("%d",solve( cut ));
	return 0;
}